Nous allons maintenant étudier le concept de programmation dynamique que nous utiliserons pour trouver les solutions à nos problèmes d'apprentissage par renforcement en utilisant les équations de Bellman.
D'une manière générale, la programmation dynamique est une manière de déployer un algorithme afin qu'il s'exécute le plus rapidement possible. L'amélioration des performances est directement liée au fait de sauvegarder des données intermédiaires en mémoire issues de la répétition de calculs (refaire les mêmes calculs encore et encore) jusqu'à ce que l'algorithme converge vers la solution. Le fait de sauvegarder les résultats de ces calculs à répétition permet d'améliorer le temps d'exécution du processus.
La programmation dynamique est également appelée optimisation dynamique. Elle peut être vue comme une méthode qui consiste à décomposer un problème complexe en plusieurs sous-problèmes plus simples, de les solutionner et de sauvegarder les résultats obtenus en mémoire. Si l'algorithme principal rencontre le même genre de sous-problème, il suffira de recharger le résultat utile depuis la mémoire.
Pour pouvoir utiliser la méthode programmation dynamique dans le but de solutionner un problème, celui-ci doit remplir deux conditions:
Le problème principal doit pouvoir être divisé en plusieurs sous-problèmes. En effet, comme nous l'avons déjà vu, la programmation dynamique est utilisée lorsqu'il faut refaire les mêmes calculs encore et encore. Les résultats intermédiaires sont sauvegardés en mémoire et donc il ne sera pas utile de refaire les calculs.
Le problème à résoudre doit avoir une sous-structure optimale, c'est-à-dire que la solution optimale du problème peut être obtenue en utilisant les solutions optimales des sous-problèmes. Par exemple, le problème du "chemin le plus court" possède une sous-structure optimale : Si un noeud x appartient au chemin le plus court depuis un noeud A vers une destination B, alors le chemin le plus court de A vers B est une combinaison des chemins les plus courts de A vers x et de x vers B.